Algorithms by Robert Sedgewick

Author:Robert Sedgewick [Sedgewick, Robert]
Language: eng
Format: epub, pdf
Publisher: Addison Wesley
Published: 2014-01-22T13:14:37+00:00

472

CHAPTER 3 ■ Searching

Clustering. The average cost of linear probing depends on the way in which the entries

clump together into contiguous groups of occupied table entries, called clusters, when

they are inserted. For example, when the key C is inserted

in our example, the result is a cluster ( A C S ) of length

9 / 64 chance of new key

hitting this cluster

3, which means that four probes are needed to insert H

before

because H hashes to the first position in the cluster. Short

key lands here

clusters are certainly a requirement for efficient perfor-in that event

mance. This requirement can be problematic as the table

fills, because long clusters are common. Moreover, since

and forms a much

longer cluster

after

all table positions are equally likely to be the hash value

of the next key to be inserted (under the uniform hashing assumption), long clusters are more likely to increase

Clustering in linear probing (M = 64)

in length than short ones, because a new key hashing to

any entry in the cluster will cause the cluster to increase

in length by 1 (and possibly much more, if there is just one table entry separating the

cluster from the next one). Next, we turn to the challenge of quantifying the effect of

clustering to predict performance in linear probing, and using that knowledge to set

design parameters in our implementations.

linear probing

random

= 1 / 2

long clusters are common

keys[0..127]

= 1 / 4

keys[8064..8192]

Table occupancy patterns (2,048 keys, tables laid out in 128-position rows)

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.